﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Diagnostics;
using System.Reflection;

namespace TSP
{    
    public class BranchBound
    {        
        private int _maxIndex = 1;
        private int[] _X, _bestWay;       
        private bool[] _free;
        private float _minSpending;        
        private float[] _T;
        private int[] _segment;

        public delegate float CalculateDistance(int city1, int city2);
        public CalculateDistance calDistance;
        public delegate void WriteFile(string fileName, int[] chromo, float fitness, Stopwatch time);
        public WriteFile writeFile;

        public float MinSpending
        {
            get { return _minSpending; }
            set { _minSpending = value; }
        }
        public int[] BestWay
        {
            get { return _bestWay; }
            set { _bestWay = value; }
        }

        public BranchBound(int maxInd)
        {
            _maxIndex = maxInd;            
        }

        public void init()
        {           
            _minSpending = float.MaxValue;
            _X = new int[_maxIndex];
            _bestWay = new int[_maxIndex];
            _free = new bool[_maxIndex];
            _T = new float[_maxIndex + 1];
            for (int i = 0; i < _maxIndex; i++)
            {
                _free[i] = true;
            }
            _free[0] = false;//thanh pho dau tien (0) da duoc di qua
            _X[0] = 1;//xuat phat tu thanh pho 1
            _T[0] = 0;//chi phi bang 0
        }

        public void initGA(Chromosome chro, int start, int len)
        {            
            _X = new int[len];
            _bestWay = new int[len];
            _free = new bool[len];
            _T = new float[len + 1];
            _segment = new int[len];
            for (int i = 0; i < len; i++)
            {
                _free[i] = true;
                _bestWay[i] = 0;
            }
            int j = 0;
            for (int i = start; i < start + len; i++)
            {
                _segment[j] = chro.chromo[i];
                j++;
            }
            _minSpending = 0;
            for (int i = 0; i < len - 1; i++)
            {
                _minSpending += calDistance(_segment[i] - 1, _segment[i + 1] - 1);
            }
            //if ((start == 0) && (start + len <= _maxIndex - 1))
            if (start == 0)
            {
                _minSpending += calDistance(_segment[len - 1] - 1, chro.chromo[start + len] - 1);
            }
            else
            {
                if (start + len == _maxIndex)
                {
                    _minSpending += calDistance(chro.chromo[start - 1] - 1, _segment[0] - 1);
                }
                else
                {
                    _minSpending += calDistance(chro.chromo[start - 1] - 1, _segment[0] - 1) + calDistance(_segment[len - 1] - 1, chro.chromo[start + len] - 1);
                }
            }          
        }

        public void attempt(int i)
        {            
            for (int j = 2; j <= _maxIndex; j++)
            {
                if (_free[j-1])
                {
                    _X[i] = j;
                    _T[i] = _T[i - 1] + calDistance(_X[i - 1] - 1, j - 1);
                    if (_T[i] < _minSpending)
                    {
                        if (i < _maxIndex-1)
                        {
                            _free[j-1] = false;                            
                            attempt(i + 1);
                            _free[j-1] = true;                               
                        }
                        else
                        {
                            float dist = calDistance(_X[_maxIndex-1]-1, 0);                            
                            if (_T[_maxIndex-1] +  dist < _minSpending)
                            {
                                //_bestWay = _X;
                                Array.Copy(_X, _bestWay, _maxIndex);
                                _minSpending = _T[_maxIndex-1] + dist;                                
                            }                          
                        }//else
                    }//if
                }//if
            }//for
        }

        //startCity: thanh pho lien truoc thanh pho bat dau cua doan _segment
        //endCity: thanh pho lien sau cua thanh pho bat dau cua doan _segment
        public void attemptGA(int i, int startCity, int endCity, int len)
        {           
            for (int j = 1; j <= len; j++)
            {
                if (_free[j - 1])
                {
                    _X[i] = j;
                    if (i == 0)
                    {
                        _T[i] = 0;
                    }
                    else
                    {
                        _T[i] = _T[i - 1] + calDistance(_segment[_X[i - 1] - 1] - 1, _segment[_X[i] - 1] - 1);
                    }                                        
                    if (_T[i] + calDistance(startCity - 1, _segment[_X[0] - 1] - 1) < _minSpending)
                    {
                        if (i < len - 1)
                        {
                            _free[j - 1] = false;
                            attemptGA(i + 1, startCity, endCity, len);
                            _free[j - 1] = true;
                        }
                        else
                        {
                            float dist = calDistance(startCity - 1, _segment[_X[0] - 1] - 1) + calDistance(_segment[_X[len - 1] - 1] - 1, endCity - 1);
                            if (_T[len - 1] + dist < _minSpending)
                            {                                
                                Array.Copy(_X, _bestWay, len);
                                _minSpending = _T[len - 1] + dist;                                                           
                            }
                        }//else
                    }//if
                }//if
            }//for
        }

        //thay the cac thanh pho trong chr boi thanh pho tot hon duoc tim ra khi su xung attempGA
        public void replaceCities(ref Chromosome chr, int start, int len)
        {
            if (_bestWay[0] != 0)
            {
                int j = 0;
                for (int i = start; i < start + len; i++)
                {
                    chr.chromo[i] = _segment[_bestWay[j] - 1];
                    j++;
                }
            }            
        }
        public void mainBranchBound()
        {           
        }

    }
}
